package company;

import java.util.Scanner;

/**
 * 5 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 * <p>
 * 输入：s = "cbbd"
 * 输出："bb"
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母组成
 */
public class LongestPalindrome5 {
    public static void main(String[] args) {
        // 输入
        Scanner scanner = new Scanner(System.in);
        String word = scanner.nextLine();
        System.out.println(longestPalindrome(word));
    }

    private static String longestPalindrome(String s) {
        // 设定指针
        int left = 0;
        int right = 0;
        int starMax = 0;
        int len = 1;
        int maxtLen = 0;
        int strLen = s.length();
        // 如果是只有一个字母，那直接输出
        if (strLen == 1) {
            return s;
        }
        // 关键点，以每个字符作为三个字符中间那个
        for (int i = 0; i < strLen; i++) {
            left = i - 1;
            right = i + 1;
            // 关键点2 以每个字母作为中间点，进行向左右扩散

            // 判断左指针--1 是否和中间指针相等
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                left--;
                len++;
            }
            // 判断中间指针是否和右指针++1相等
            while (right < strLen && s.charAt(right) == s.charAt(i)) {
                right++;
                len++;
            }

            // 判断左右指针是否相等
            while (left >= 0 && right < strLen && s.charAt(right) == s.charAt(left)) {
                right++;
                left--;
                len += 2;
            }
            if (len > maxtLen) {
                maxtLen = len;
                starMax = left;
            }
            len = 1;
        }
        return s.substring(starMax + 1, starMax + maxtLen + 1);
    }

    private static String longestPalindromeTwo(String s) {
        int left = 0;
        int right = 0;
        int start = 0;
        int len = 0;
        int maxtLen = 0;
        int length = s.length();
        // 关键点，以每个字符作为三个字符中间那个
        for (int i = 0; i < s.length(); i++) {
            left = i - 1;
            right = i + 1;

            // 关键点2 以每个字母作为中间点，进行向左右扩散
            while (left > 0 && s.charAt(left) == s.charAt(i)) {
                --left;
                ++len;
            }

            while (right < length && s.charAt(right) == s.charAt(i)) {
                right++;
                ++len;
            }

            while (right < length && left > 0 && s.charAt(right) == s.charAt(i)) {
                ++right;
                --left;
                len += 2;
            }

            // 记录最大的长度 开始位置
            if (maxtLen < len) {
                maxtLen = len;
                start = left;
            }
        }
        return s.substring(Math.max(start, 0) + 1, start + len + 1);
    }
}
